package doublePoint;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @program: leetcode
 * @description: 将两个升序数组合并为一个新的 升序 数组并返回。新数组是通过拼接给定的两个数组的所有元素组成的。
 *  * 示例 1：
 *  * 输入：l1 = [1,2,4], l2 = [1,3,4]
 *  * 输出：[1,1,2,3,4,4]
 *  * 示例 2：
 *  * 输入：l1 = [], l2 = []
 *  * 输出：[]
 *  * 示例 3：
 *  * 输入：l1 = [], l2 = [0]
 *  * 输出：[0]
 * @author: lxf
 * @create: 2024-03-15 08:34
 **/
public class MergeTwoLists {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int l1 = 0,l2 = 0;
        //l1作为被插入方，l2作为插入方，
        //采用双指针的方法，让l2的值插入到l1中，条件为l2<l1，插入到前方
        //如果l1>l2，证明l2的值比l1的最小值都小，插入到此时l1的前面，此时l1所指位置应当不变，（l1值++），l2继续往后挪
        //如果l1<l2，l1++，继续往后找比l2值大的
        //两种情况都需要变化l1指针位置，第一种是插入后，所指值会后挪，第二中是不符合条件，继续后挪
        while (l1 < m+n && l2 <n){
            if (nums1[l1] > nums2[l2]){
                move(nums1,l1,nums2[l2]);
                l2++;
            }
            l1++;
        }
        //此时看l2有没有被插完，没插完的将剩下的元素覆盖l1中的后面的值
        if (l2 < n){
            //此时l1的值为m+n，即总数组元素，
            //n-l2，是看l2中还剩几个元素
            l1 = l1 - (n-l2);
            while (l2<n){
                nums1[l1++] = nums2[l2++];
            }
        }
    }

    public static void move(int[] nums1,int index,int num){
        //从后往前覆盖，倒数第二个赋值给倒数第一个，以此类推
        int point = nums1.length -1 -1;
        while (point >= index){
            nums1[point+1] = nums1[point];
            point--;
        }
        nums1[index] = num;
//        nums1 = Arrays.copyOf(nums1, nums1.length + 1);
//        System.arraycopy(nums1,index,nums1,index+1,nums1.length-index-1);
//        nums1[index] = num;
//        return nums1;
    }

    public static void main(String[] args) {
        int[] num1 = new int[]{1,2,3,0,0,0};
        int[] num2 = new int[]{2,5,6};
        int[] num3 = new int[]{0};
        int[] num4 = new int[]{1};
        int[] num5 = new int[]{-1,0,0,3,3,3,0,0,0};
        int[] num6 = new int[]{1,2,2};
        merge3(num3,0,num4,1);
    }

    //创建新的数组保存
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        int[] newNum = new int[m+n];
        if (n == 0){newNum = nums1;}
        if (m == 0){newNum = nums2;}
        int l1 = 0,l2 = 0,i = 0;
        while (i < m+n && l2 < n && l1 < m){
            if (nums1[l1] > nums2[l2]){
                newNum[i] = nums2[l2];
                l2++;
            }else {
                newNum[i] = nums1[l1];
                l1++;
            }
            i++;
        }
        if (l2 < n){
            while (l2<n){
                newNum[i++] = nums2[l2++];
            }
        }
        if (l1 < m){
            while (l1<m){
                newNum[i++] = nums1[l1++];
            }
        }
        for (int i1 = 0; i1 < m + n; i1++) {
            nums1[i1] = newNum[i1];
        }
    }

    //将list2插入到list1中改进版本
    //空间复杂度O(m+n),创建新数组再赋值给num1
    public static void merge3(int[] nums1, int m, int[] nums2, int n) {
        int[] newNum = new int[m+n];
        int l1 = 0,l2 = 0,i = 0;
        int num = 0;
        while (l1 < m || l2 < n){
            //如果l1到底，后面接着赋值l2
            if (l1 == m){
                num = nums2[l2++];
            //如果l2到底，后面接着赋值l1
            }else if (l2 == n){
                num = nums1[l1++];
            }else if (nums1[l1] > nums2[l2]){
                num = nums2[l2++];
            }else {
                num = nums1[l1++];
            }
            newNum[i++] = num;
        }
        for (int i1 = 0; i1 < m + n; i1++) {
            nums1[i1] = newNum[i1];
        }
    }
}
